package Greddy;

import java.util.ArrayList;
import java.util.List;

/**
 * 738.单调递增的数字
 * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
 * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
 */
public class monotoneIncreasingDigits {
    /**
     * 一刷二刷思路一致，看二刷
     */
    public static int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
    /**
     * 二刷
     */
    public int monotoneIncreasingDigits2(int n) {
        // 转换成字符数组，方便处理每一位
        char[] chars = String.valueOf(n).toCharArray();

        // 标记需要变成9的起始位置
        int flag = chars.length;

        // 从右往左遍历，找到第一个不满足递增的位置
        for (int i = chars.length - 1; i > 0; i--) {
            if (chars[i - 1] > chars[i]) {
                flag = i;  //相当于把后面的都变为9
                chars[i - 1]--; //减1
            }
        }

        // 将flag位置及其后面的所有数字变成9
        for (int i = flag; i < chars.length; i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(new String(chars));
    }
}
